//
//  main.cpp
//  BTree
//
//  Created by mac on 2020/5/13.
//  Copyright © 2020 DDI. All rights reserved.
//

#include <iostream>
using namespace std;
#define MaxSize 100

typedef char ElemType;
typedef struct node {
    ElemType data;
    struct node *lchild;
    struct node *rchild;
} BTNode;

/*括号法输入二叉树转化为链式存储*/
void CreatBTree(BTNode *&bc, char *c) {
    
    BTNode *BS[MaxSize], *p = nullptr;      //BS为一整棵二叉树，p为临时结点
    /*top为BS的指针，指向双亲节点，j为数组的指向，k为左右结点的标识*/
    int top = -1, j = 0, k = 0;
    char ch;                            //ch为数组的元素
    bc = NULL;                          //初始化二叉树为空
    ch = c[j];                          //获取第一个数组元素
    
    while (ch != '\0') {                //开始循环建树，直到数组的最后退出
        switch (ch) {
            case '(':                   //遇到左括号，处理左孩子
                top++;                  //指针指向双亲节点
                k = 1;                  //k指向左孩子
                BS[top] = p; break;     //上一个结点为双亲节点
            case ')':                   //遇到右括号，该点的子结点处理完毕
                top--; break;           //回溯到上一个结点
            case ',':                   //遇到‘，’号，处理右节点
                k = 2; break;           //k指向右节点
            default:                    //遇到字母，开始创建节点
                p = new BTNode;         //创建新节点，p指向他
                p->data = ch;           //存放节点的值
                p->lchild = p->rchild = NULL;       //节点的左右节点设为空
                if (bc == NULL)         //如果没有跟节点
                    bc = p;             //p指向的节点设为跟节点
                else                    //已有跟节点
                    switch (k) {        //判断储存为左节点还是右节点
                        case 1:
                            BS[top]->lchild = p; break;     //p存为左节点
                        case 2:
                            BS[top]->rchild = p; break;     //p存为右节点
                        default: break;
                    }
                break;
        }
        
        j++;                //循环数组
        ch = c[j];
    }
    
}

/*括号表示法输出该树*/
void DisplayBTree(BTNode *bd) {
    if (bd != NULL) {
        cout<<bd->data;                 //输出双亲节点
        if (bd->lchild != NULL || bd->rchild != NULL) {     //子节点都不为空时进行
            cout<<'(';                  //输出左括号
            DisplayBTree(bd->lchild);   //递归左节点
            if (bd->rchild != NULL)     //如果有右节点输出’，‘；
                cout<<',';
            DisplayBTree(bd->rchild);   //递归右节点
            cout<<')';                  //输出’）‘；
        }
    }
}

/*输入一个节点，输出它的左右孩子*/
bool FindChild(BTNode *bf, ElemType e) {
    if (bf == NULL)                     //节点到低端，没有找到目标节点，返回false
        return false;
    else if (bf->data == e) {           //找到目标节点
        if (bf->lchild == NULL)         //左节点为空输出空
            cout<<e<<"的左节点：NULL"<<endl;
        else                            //左节点不为空，输出节点值
            cout<<e<<"的左节点："<<bf->lchild->data<<endl;
        if (bf->rchild == NULL)         //右节点为空输出空
            cout<<e<<"的右节点：NULL"<<endl;
        else                            //右节点不为空，输出节点值
            cout<<e<<"的右节点："<<bf->rchild->data<<endl;
        return true;                    //找到目标节点，返回true
    } else {
        /*设置一个flag来标记有无找到目标节点，并进行左孩子递归*/
        bool flag = FindChild(bf->lchild, e);
        if (flag)                       //已找到节点，返回true
            return true;
        else                            //左节点没有找到，递归寻找右节点
            return FindChild(bf->rchild, e);
    }
}

/*输出该二叉树的高度*/
int BTHight(BTNode *bh) {
    int l = 0, r = 0;               //l记录左节点的高度，r记录右节点的高度
    if (bh == NULL) return 0;       //空树或到底返回0
    else {
        l = BTHight(bh->lchild);        //求左节点的高度
        r = BTHight(bh->rchild);        //求右节点的高度
        return l > r ? l+1 : r+1;       //返回较大的孩子节点加上跟节点(本身)
    }
}

/*输出该二叉树结点的个数*/
int BTCount(BTNode *bc) {
    if (bc == NULL)            //节点为空，返回0
        return 0;
    else                        //本身节点加一，递归寻找孩子节点
        return BTCount(bc->lchild) + BTCount(bc->rchild) + 1;
}

/*输出该二叉树双分支结点的个数*/
int BTDouble(BTNode *bd) {
    if (bd == NULL)         //空节点，返回0
        return 0;
    if (bd->lchild != NULL && bd->rchild != NULL)  //有两个孩子节点，总数加一
        return BTDouble(bd->lchild) + BTDouble(bd->rchild) + 1;
    else                                            //递归寻找
        return BTDouble(bd->lchild) + BTDouble(bd->rchild);
}

/*输出该二叉树单分支结点的个数
 跟双分支的一样，不同的是判断加一的条件变为：其中一个为空另一个不为空*/
int BTSingle(BTNode *bs) {
    if (bs == NULL)
        return 0;
    if ((bs->lchild != NULL && bs->rchild == NULL) || (bs->lchild == NULL && bs->rchild != NULL))
        return BTSingle(bs->lchild) + BTSingle(bs->rchild) + 1;
    else
        return BTSingle(bs->lchild) + BTSingle(bs->rchild);
}

/*输出该二叉树叶子结点的个数
 跟单分支的一样，不同的是判断加一的条件变为：左右孩子都为空；且叶子节点不需要再递归，直接返回1*/
int BTLeaf(BTNode *bl) {
    if (bl == NULL)
        return 0;
    if (bl->lchild == NULL && bl->rchild == NULL)
        return 1;
    else
        return BTLeaf(bl->lchild) + BTLeaf(bl->rchild);
}

/*输出该二叉树的宽度
 利用两个函数求宽度，一个遍历求每层的个数，一个求各个层数的最大值*/
/*函数一：遍历各个层数，求各个层数的个数*/
void Width(BTNode *w,int W[],int level)
{
    if (w == NULL)      //为空时直接返回
        return;
    else {
        W[level]++;         //进入下一层
        Width(w->lchild,W,level+1);     //遍历左孩子的下一层，同时此层个数加一
        Width(w->rchild,W,level+1);     //遍历右孩子的下一层，同时此层个数加一
    }
}

/*函数二：求出最大值*/
int BTWidth(BTNode *bw)
{
    if(bw == NULL)          //二叉树为空，返回0
        return 0;
    else {
        int W[MaxSize] = {0};       //定义一个数组W来记录各个层的个数
        int MaxW=0;                 //定义MaxW记录最大值
        Width(bw, W, 0);            //遍历二叉树
        for(int i=0;W[i]!=0;i++)    //求所有层个数的最大值
            if(W[i]>MaxW)
                MaxW=W[i];
        return MaxW;                //返回最大值
    }
}

/*任意给定该二叉树的两个结点，输出它们的最近的公共祖先
 可转化为寻找一个节点上是否含有所有目标节点*/
BTNode* lowestCommonAncestor(BTNode* ba, ElemType p, ElemType q) {
    if(ba == NULL || ba->data == p || ba->data == q)//遇到目标节点或空节点，返回，不用继续寻找
        return ba;
    
    BTNode* left=lowestCommonAncestor(ba->lchild, p, q);    //递归寻找左子树
    BTNode* right=lowestCommonAncestor(ba->rchild, p, q);   //递归寻找右子树
    
    if(left == NULL && right == NULL)       //左右子树都找不到，返回空
        return NULL;
    else if(left&&!right)return left;   //左子树找到返回左子树,右子树找到返回右子树
    else if(right&&!left)return right;
    
    return ba;          //左右子树都能找到，返回本节点
}

/*销毁二叉树*/
void DestroyBTree(BTNode *&bd) {
    if (bd != NULL) {
        DestroyBTree(bd->lchild);       //递归释放左子树
        DestroyBTree(bd->rchild);       //递归释放右子树
        free(bd);                       //释放空间
    }
}


int main() {
    BTNode *btree;
    char str[MaxSize];
    ElemType e, e2, e3;
    
    cout<<"请输入一个括号表示法的二叉树以创建二叉树并以'*'结束："<<endl;
    int i = 0;
    char c;
    while (cin>>c) {
        if (c == '*')
            break;
        str[i] = c;
        i++;
    }
    
    /*创建二叉树*/
    CreatBTree(btree, str);
    cout<<endl;
    
    cout<<"1.括号表示法输出该树"<<endl;
    DisplayBTree(btree);
    cout<<endl<<endl;
    
    cout<<"2.输入一个结点的值，输出该结点的左，右孩子的值"<<endl;
    cout<<"请输入节点是值：";cin>>e;
    if (!FindChild(btree, e))
        cout<<"本二叉树无该节点"<<endl;
    cout<<endl;
    
    cout<<"3.输出该二叉树的高度"<<endl;
    cout<<BTHight(btree);
    cout<<endl<<endl;
    
    cout<<"4.输出该二叉树结点的个数"<<endl;
    cout<<BTCount(btree)<<endl;
    cout<<endl;
    
    cout<<"5.输出该二叉树双分支结点的个数"<<endl;
    cout<<BTDouble(btree)<<endl;
    cout<<endl;
    
    cout<<"6.输出该二叉树单分支结点的个数"<<endl;
    cout<<BTSingle(btree)<<endl;
    cout<<endl;
    
    cout<<"7.输出该二叉树叶子结点的个数"<<endl;
    cout<<BTLeaf(btree)<<endl;
    cout<<endl;
    
    cout<<"8.输出该二叉树的宽度"<<endl;
    cout<<BTWidth(btree)<<endl;
    cout<<endl;
    
    cout<<"9.任意给定该二叉树的两个结点，输出它们的最近的公共祖先"<<endl;
    cout<<"请输入两个节点的值："; cin>>e2>>e3;
    if (!lowestCommonAncestor(btree, e2, e3))
        cout<<"输入有误，本二叉树查无该节点"<<endl;
    else
        cout<<"最近的公共祖先为："<<lowestCommonAncestor(btree, e2, e3)->data<<endl;
    cout<<endl;
    
    cout<<"10.销毁该二叉树"<<endl;
    DestroyBTree(btree);
    cout<<endl;
    
    return 0;
    
}
